import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.*;

public class AC {
    public static class ACNode{
        // child存放子节点
        private HashMap<Character,ACNode> child;
        // 如果当前节点是敏感词结尾，返回敏感词长度 (在源文本中可通过长度回推出敏感词本身)
        private int endLen;
        // 失败指针
        private ACNode fail;

        public ACNode(){
            child = new HashMap<>();
            endLen = 0;
            fail = null;
        }
    }

    // 这个类用于存放匹配到的敏感词信息。
    public static class ResultNode{
        // 敏感词长度
        int len;
        // 敏感词结束位置
        int end;
        public ResultNode(int len,int end){
            this.len=len;
            this.end=end;
        }
    }


    // AC自动机的实现类
    public static class ACImpl{

        // 在类初始化时，创建根结点
        private ACNode root;
        public ACImpl(){
            root = new ACNode();
        }

        // 添加新词
        public void insert(String s){
            char[] chars = s.toCharArray();
            // curNode 指向当前节点
            ACNode curNode = root;
            for(int i=0; i<chars.length;i++){
                //  未在子结点中获取到该字符的节点，则在创建新的节点
                if(curNode.child.get(chars[i]) == null)
                    curNode.child.put(chars[i],new ACNode());
                //  当前节点指针后移
                curNode = curNode.child.get(chars[i]);
            }
            //  当前节点可作为结束节点
            curNode.endLen = s.length();
        }

        //  构建fail指针
        public void buildFailPoint(){
            // 使用队列广度优先给每一层的节点设置fail节点
            Queue<ACNode> queue = new LinkedList<>();
            queue.add(root);

            // cur:当前节点， node:当前节点的子节点， fail:用于回推失败节点
            ACNode cur=null, node=null, fail=null;

            while (!queue.isEmpty()){
                cur = queue.poll();
                fail = cur.fail;
                //  遍历map集合（所有子节点）
                for(Map.Entry<Character, ACNode> c : cur.child.entrySet()){
                    //  获取子节点，并初始化子节点的fail节点为root
                    node = cur.child.get(c.getKey());
                    node.fail = root;
                    //  循环遍历回推失败节点
                    while (fail!=null) {
                        if(fail.child.get(c.getKey())!=null){
                            node.fail=fail.child.get(c.getKey());
                            break;
                        }
                        else
                            fail=fail.fail;
                    }
                    queue.add(node);
                }
            }
        }

        //  查找文本敏感词，并以链表返回敏感词集合。
        public List<String> search(String s){
            List<String> res = new ArrayList<>();
            ACNode cur = root, fail;
            char c;
            // 遍历文本
            for(int i=0;i<s.length();i++){
                c = s.charAt(i);
                while (cur!=root && cur.child.get(c)==null){
                    cur = cur.fail;
                }

                if(cur.child.get(c)!=null){
                    cur = cur.child.get(c);
                    if(cur.endLen!=0)
                        res.add(s.substring(i-cur.endLen+1,i+1));
                }
            }
            return res;
        }

        //  返回每个敏感词的位置和长度
        public List<ResultNode> searchNode(String s){
            List<ResultNode> res = new ArrayList<>();
            ACNode cur = root, fail;
            char c;
            // 遍历文本
            for(int i=0;i<s.length();i++){
                c = s.charAt(i);
                while (cur!=root && cur.child.get(c)==null){
                    cur = cur.fail;
                }

                if(cur.child.get(c)!=null){
                    cur = cur.child.get(c);
                    if(cur.endLen!=0)
                        res.add(new ResultNode(cur.endLen,i+1));
                }
            }
            return res;
        }

        // 将所有铭感词用*替换
        public String replace(String text){
            StringBuffer sb = new StringBuffer(text);
            List<ResultNode> rn = searchNode(text);
            for(ResultNode r : rn){
                sb.replace(r.end-r.len,r.end,makeStar(r.len));
            }
            return sb.toString();
        }

        // 生成给定长度的*
        public String makeStar(int n){
            StringBuffer sb = new StringBuffer();
            for(int i=0;i<n;i++){
                sb.append("*");
            }
            return sb.toString();
        }
    }



    public static void main(String[] args) {
        ACImpl ac = new ACImpl();
        String path = ".\\敏感词库";
        File dir = new File(path);
        File[] files = dir.listFiles();
        String line;
        for(File file:files){
            try{
                BufferedReader reader = new BufferedReader(new FileReader(file));
                while ((line = reader.readLine())!=null){
                    if(!line.trim().isEmpty()){
                        ac.insert(line.trim());
                    }
                }
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
        ac.buildFailPoint();

        Scanner sc = new Scanner(System.in);
        String text;
        text="测试案例：TNND测试一下";
        System.out.println(ac.replace(text));
        while (true){
            System.out.println("请输入测试文本：");
            text = sc.nextLine();
            System.out.println(ac.replace(text));
        }
    }
}
